#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    // 1. 只有一次买入卖出的交易
    int maxProfit(vector<int>& prices) {
        if (prices.size() == 1) return 0;
        int max_here = 0;
        int max_sofar = 0;
        for (int i=1; i<prices.size(); ++i) {
            max_here += prices[i]-prices[i-1];
            if (max_here > max_sofar) max_sofar = max_here;
            if (max_here < 0) max_here = 0;
        }
        return max_sofar;
    }


    // 2. 尽可能地多次交易 (时间需要错开) [122]
    // Greedy algorithm: 直接累加上升区间！
    int maxProfitMulti(vector<int>& prices) {
        int n = prices.size();
        if (n <= 1) return 0;
        int accu_sofar = 0;
        for (int i=1; i<n; ++i) {
            int dif = prices[i] - prices[i-1];
            if (dif > 0) accu_sofar += dif;
        }
        return accu_sofar;
    }
};


int main(void) {
    Solution soln = Solution();
    vector<int> nums = {1,7,5,8};
    cout << soln.maxProfitMulti(nums);
}
